The present invention relates generally to storing matrices in computer memory, and more specifically, to sparsity-driven selection of data structures for storing matrices in computer memory.
Matrices and linear algebra operations are the building blocks for a broad class of supervised and unsupervised machine learning algorithms. Machine learning algorithms that use such operations include non-negative matrix factorization (NMF), single value decomposition (SVD), linear regression, logistic regression, hypertext induced topic selection (HITS), and support vector machines (SVMs).
A sparse matrix is a matrix that is populated primarily with zeros. By contrast, if a larger number of elements differ from zero, then it is common to refer to the matrix as a dense matrix. The fraction of non-zero elements to all elements in a matrix is called the sparsity or density of the matrix.
There are a variety of matrix representations in use today such as: compressed sparse row (CSR) which includes three fixed length arrays; compressed sparse column (CSC) which is similar to CSR but for columns; list of lists (LIL) which stores one list per row, where each entry stores a column index and value; and dictionary of keys (DOK) which represents non-zero values as a dictionary mapping.
The data structures used to store matrices or blocks of matrices have an impact on both the performance and memory footprint associated with linear algebra operations.